package com.everyday.algorithm.changyf.leetcode.editor.cn.zuo;

public class AVLTree<T extends Comparable<T>> {

    Node head;



    void add(T t){
        if (head == null) {
           head = new Node(t);
           return;
        }
        head = head.add(head, t);
    }
    void del(T t){
        head.del(head, t);

    }
    void search(T t){
        Node search = head.search(head, t);
        System.out.println("search = " + search);
    }
    void print(){
        head.print(head, head.h);
    }



    public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<Integer>();
        avlTree.add(1);
        avlTree.print();
        System.out.println("-----------------");
        avlTree.add(2);
        avlTree.print();
        System.out.println("-----------------");
        avlTree.add(3);
        avlTree.print();
        System.out.println("-----------------");
        avlTree.add(4);
        avlTree.print();
        System.out.println("-----------------");
        avlTree.add(5);
        avlTree.print();
        System.out.println("-----------------");
        avlTree.add(6);
        avlTree.print();
    }






    // 树节点
    class Node {
        T v;
        int h;
        Node l;
        Node r;

        Node() {
        }

        Node(T v) {
            this.v = v;
            this.h = 1;
            this.l = null;
            this.r = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "v=" + v +
                    ", h=" + h +
                    ", l=" + l +
                    ", r=" + r +
                    '}';
        }

        void print(Node node, int num) {

            for (int i = 0; i < num; i++) {
                System.out.print(" ");
            }
            System.out.print(node.v);
            System.out.print(" ");
            if (node.l != null) {
                System.out.println();
                print(node.l,num - 1);
            }

            if (node.r != null) {
                print(node.r,num + 1);
            }

            System.out.println();
        }

        /**
         * 搜索某个值
         * @param cur
         * @param o
         * @return
         */
        Node search(Node cur, T o) {
            if (cur == null) {
                return null;
            }
            if (cur.v.compareTo(o) == 0) {
                return cur;
            } else if (cur.v.compareTo(o) > 0) {
                return search(cur.l, o);
            } else{
                return search(cur.r, o);
            }
        }


        /**
         * 增加一个节点，调整
         * @param cur
         * @param o
         */
        Node add(Node cur, T o) {
            if (cur == null) {
                return new Node(o);
            }
            if (cur.v.compareTo(o) > 0) {
                cur.l = add(cur.l, o);
            } else if (cur.v.compareTo(o) < 0) {
                cur.r = add(cur.r, o);
            } else {
                throw new RuntimeException("不能插入重复的值");
            }

            int hl = cur.l == null ? 0 : cur.l.h;
            int hr = cur.r == null ? 0 : cur.r.h;
            cur.h = Math.max(hl, hr) + 1;

            return revise(cur);
        }

        /**
         * 删除一个节点，调整
         * @param o
         */
        Node del(Node cur, T o) {

            //如果左右都有，判断高度
            //如果左边不在，找后继
            //如果右边不在找前继
            //其他直接返回null
            if (cur.v.compareTo(o) == 0) {
                int hl = cur.l == null ? 0 : cur.l.h;
                int hr = cur.r == null ? 0 : cur.r.h;

                if (hr != 0 && hr >= hl) {
                    return delSuccessor(cur.r);
                } else if (hl != 0 && hl > hr) {
                    return delPredecessor(cur.l);
                } else {
                    return null;
                }
            }

            if (cur.v.compareTo(o) > 0) {
                del(cur.l, o);
                cur.h = Math.max(cur.h, cur.l.h + 1);
                cur.l = revise(cur.l);

            } else if (cur.v.compareTo(o) < 0) {
                del(cur.r, o);
                cur.h = Math.max(cur.h, cur.r.h + 1);
                cur.r = revise(cur.r);
            } else {
                throw new RuntimeException("不能插入重复的值");
            }
            return cur;

        }


        Node revise(Node cur) {
            int hl = cur.l == null ? 0 : cur.l.h;
            int hr = cur.r == null ? 0 : cur.r.h;
            if (hl - hr > 1) {
                cur = rHand(cur);
            } else if (hl - hr < -1) {
                cur = lHand(cur);
            }
            return cur;
        }
        //右旋
        Node rHand(Node cur) {
            Node t = cur.l;
            //

            cur.l = t.r;
            int chl = cur.l == null ? 0 : cur.l.h;
            int chr = cur.r == null ? 0 : cur.r.h;
            cur.h = Math.max(chr, chl) + 1;

            t.r = cur;
            int thl = t.l == null ? 0 : t.l.h;
            int thr = t.r == null ? 0 : t.r.h;
            t.h = Math.max(thl, thr) + 1;

            return t;
        }
        //左旋
        Node lHand(Node cur) {
            Node t = cur.r;
            cur.r = t.l;

            int chr = cur.r == null ? 0 : cur.r.h;
            int chl = cur.l == null ? 0 : cur.l.h;
            cur.h = Math.max(chl, chr) + 1;
            t.l = cur;
            int thl = t.l == null ? 0 : t.l.h;
            int thr = t.r == null ? 0 : t.r.h;
            t.h = Math.max(thr, thl) + 1;
            return t;
        }

        // 删除并返回前继节点
        Node delPredecessor(Node cur) {
            if (cur.r == null) {
                Node t = cur;
                cur = null;
                return t;
            } else {
                return delPredecessor(cur.r);
            }
        }

        // 删除并返回后继节点
        Node delSuccessor(Node cur) {
            return cur;
        }
    }


}

